package main

import (
	"fmt"
	"math"
)

// 观察测试用例可以知道。 最小的组合一定是 {nums1[0], nums2[0]}
// 但往下就会有两种情况：nums2[1]， nums2[0]。 或者 nums1[0], nums2[1]
// 需要进行判断，用哪一个，双指针即可
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
	rst := [][]int{{nums1[0], nums2[0]}}
	n1, n2 := len(nums1), len(nums2)
	// 1. 如果只要一个值，那直接就是返回  {nums1[0], nums2[0]} 就可以了
	if k == 1 {
		return rst
	}
	// 2. 细节： k 值，可能大于总的组合数
	if k > n1 * n2 {
		k = n1 * n2
	}
	for i, j := 0, 0; k - 1 > 0; k-- {
		// 3. 记录两种情况下，那个值最小
		min1 := math.MaxInt32
		min2 := math.MaxInt32
		if i + 1 < n1 {
			min1 = nums1[i + 1] + nums2[j]
		}
		if j + 1 < n2 {
			min2 = nums2[j + 1] + nums1[i]
		}
		// 4. 谁小，记录谁，且移动i， j
		if min1 < min2 {
			i++
		} else {
			j++
		}
		rst = append(rst, []int{nums1[i], nums2[j]})
		fmt.Println(rst)
	}
	// 5. 返回结果
	return rst
}


func kSmallestPairs1(nums1 []int, nums2 []int, k int) [][]int {
	rst := [][]int{{nums1[0], nums2[0]}}
	n1, n2 := len(nums1), len(nums2)
	// 1. 如果只要一个值，那直接就是返回  {nums1[0], nums2[0]} 就可以了
	if k == 1 {
		return rst
	}
	// 2. 细节： k 值，可能大于总的组合数
	if k > n1 * n2 {
		k = n1 * n2
	}
	i := 0
	j := 0
	// []int{1,2,4}, []int{-1,1,2}
	for p1, p2 := 0, 0; k - 1 > 0; k-- {
		// 3. 记录四种情况下，哪个值最小
		min1 := math.MaxInt32
		min2 := math.MaxInt32
		min3 := math.MaxInt32
		min4 := math.MaxInt32
		if j < p2 {
			min1 = 	nums1[p1] + nums2[j + 1]
		}
		if p1 + 1 < n1 {
			min2 = nums1[p1 + 1] + nums2[0]
		}
		if i < p1 {
			min3 = nums1[i + 1] + nums2[p2]
		}
		if p2 + 1 < n2 {
			min4 = nums1[0] + nums2[p2 + 1]
		}
		mi := mint(min1, min2, min3, min4)

		if mi == min1 {
			i = p1
			j ++
			rst = append(rst, []int{nums1[p1], nums2[j]})
		} else if mi == min2 {
			p1 ++
			i = p1
			rst = append(rst, []int{nums1[p1], nums2[0]})
			j = 0
		} else if mi == min3 {
			i++
			rst = append(rst, []int{nums1[i], nums2[p2]})
		} else if mi == min4 {
			p2 ++
			j = p2
			rst = append(rst, []int{nums1[0], nums2[p2]})
			i = 0
		}
		if len(rst) == 3 {
			c := 1
			fmt.Println(c)
		}
		fmt.Println(rst)
	}
	// 5. 返回结果
	return rst
}


func mint(a, b, c, d int) int {
	temp := a
	if a < temp {
		temp = a
	}
	if b < temp {
		temp = b
	}
	if c < temp {
		temp = c
	}
	if d < temp {
		temp = d
	}
	return temp
}

func main() {
	//rst := kSmallestPairs1([]int{1,1,2}, []int{1,2,3}, 10)
	//rst := kSmallestPairs1([]int{1,7,11}, []int{2,4,6}, 3)
	rst := kSmallestPairs1([]int{1,2,4}, []int{-1,1,2}, 100)
	//rst := mint(5, 3 , 9, 8)
	fmt.Println(rst)
}

1 -1  2 -1  1 1   2 1   4 -1  2 1  2 2   4 1  4 2

//1 1
//1 2
//1 3
//1 1
//1 2
//1 3
//2 1
//2 2
//2 3

//                 1 0    0, 1
//				 1, 1
//
//1 2    2 1    1 2
//
//1 1
//1 1
//
//
//
//
//
//
//双指针， i j 分别对应当前nums1， nums2位置索引, 那么下一个最小的 可能是四种情况：
//
//i, m (m 从0下标递增过来)   ：i 不变和 nums2 的下一个组合（可能上一组是和 i, 0  现在 i, 1）
//i + 1, 0   ：i下一个位置， 到 nums2 的下标0 的组合
//
//相同的 j也有两种情况
//l,  j
//0, j + 1
//
//
//这四种里面比较出来， 谁是最小的， 一直这样比较到 k个
a b c
x y z

ax

bx  ay  by

cx  cy  az  bz  cz

